package com.wudeyong;

import java.io.*;
import java.util.*;

/**
 * Author :wudeyong
 * Date 2017/7/3
 * For More Information,Please Visit https://wudeyong.com
 */
public class KMeans {

    public static List<ArrayList<DataPoint>>
    initHelpCenterList(List<ArrayList<DataPoint>> helpCenterList,int k){
        for(int i=0;i<k;i++){
            helpCenterList.add(new ArrayList<DataPoint>());
        }
        return helpCenterList;
    }

    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException{

        long startTime=System.currentTimeMillis();

        List<DataPoint> centers = new ArrayList<DataPoint>();
        List<DataPoint> newCenters = new ArrayList<DataPoint>();
        List<ArrayList<DataPoint>> helpCenterList = new ArrayList<ArrayList<DataPoint>>();

        //读入原始数据
        BufferedReader br=new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\TeenTeam\\Desktop\\大数据\\data.txt")));
        String data = null;
        List<DataPoint> dataList = new ArrayList<DataPoint>();
        while((data=br.readLine())!=null){
            //System.out.println(data);
            String []fields = data.split("\t");
            DataPoint tmpPoint = new DataPoint();
            double [] dataDouble=new double[fields.length-1];
            for(int i=1; i<fields.length;i++)
                dataDouble[i-1]=Double.parseDouble(fields[i]);
            tmpPoint.setDimensioin(dataDouble);
            tmpPoint.setDataPointName(fields[0]);
            dataList.add(tmpPoint);
        }
        br.close();

        //随机确定K个初始聚类中心
        Random rd = new Random();
        int k=3;
        int [] initIndex={59,71,48};
        int [] helpIndex = {0,59,110};
        int [] givenIndex = {0,1,2};
        System.out.println("随机选择聚类中心索引");
        for(int i=0;i<k;i++){
            int index = rd.nextInt(initIndex[i]) + helpIndex[i];
            //int index = givenIndex[i];
            System.out.println("索引为： "+index);
            centers.add(dataList.get(index));
            helpCenterList.add(new ArrayList<DataPoint>());
        }


        //输出k个初始中心
        System.out.println("初始中心为:");
        for(int i=0;i<k;i++)
            System.out.println(Arrays.toString(centers.get(i).getDimensioin()));

        while(true)
        {//进行若干次迭代，直到聚类中心稳定

            for(int i=0;i<dataList.size();i++){//标注每一条记录所属于的中心
                double minDistance=99999999;
                int centerIndex=-1;
                for(int j=0;j<k;j++){//离0~k之间哪个中心最近
                    double currentDistance=0;
                    for(int t=1;t<centers.get(0).size();t++){//计算两点之间的欧式距离
                        currentDistance +=  ((centers.get(j).getDimensioin()[t]-dataList.get(i).getDimensioin()[t])/(centers.get(j).getDimensioin()[t]+dataList.get(i).getDimensioin()[t])) * ((centers.get(j).getDimensioin()[t]-dataList.get(i).getDimensioin()[t])/(centers.get(j).getDimensioin()[t]+dataList.get(i).getDimensioin()[t]));
                    }
                    if(minDistance>currentDistance){
                        minDistance=currentDistance;
                        centerIndex=j;
                    }
                }
                helpCenterList.get(centerIndex).add(dataList.get(i));
            }

            //  System.out.println(helpCenterList);

            //计算新的k个聚类中心
            for(int i=0;i<k;i++){

                DataPoint tmp = new DataPoint();
                double[] tmpDouble=new double[centers.get(0).size()];
                for(int j=0;j<centers.get(0).size();j++){
                    double sum=0;
                    for(int t=0;t<helpCenterList.get(i).size();t++)
                        sum+=helpCenterList.get(i).get(t).getDimensioin()[j];
                    tmpDouble[j]=(sum/helpCenterList.get(i).size());
                }
//                tmp.setDataPointName(helpCenterList.get(i).);
                tmp.setDimensioin(tmpDouble);
                newCenters.add(tmp);

            }

            //计算新旧中心之间的距离，当距离小于阈值时，聚类算法结束
            double distance=0;

            for(int i=0;i<k;i++){
                for(int j=1;j<centers.get(0).size();j++){//计算两点之间的欧式距离
                    distance += ((centers.get(i).getDimensioin()[j]-newCenters.get(i).getDimensioin()[j])/(centers.get(i).getDimensioin()[j]+newCenters.get(i).getDimensioin()[j])) *
                            ((centers.get(i).getDimensioin()[j]-newCenters.get(i).getDimensioin()[j])/(centers.get(i).getDimensioin()[j]+newCenters.get(i).getDimensioin()[j]));
                }

            }
            if(distance==0)//小于阈值时，结束循环
                break;
            else//否则，新的中心来代替旧的中心，进行下一轮迭代
            {
                centers = new ArrayList<DataPoint>(newCenters);
                //System.out.println(newCenters);
                newCenters = new ArrayList<DataPoint>();
                helpCenterList = new ArrayList<ArrayList<DataPoint>>();
                helpCenterList=initHelpCenterList(helpCenterList,k);
            }
        }
        //输出最后聚类结果
        for(int i=0;i<k;i++){
            System.out.println("聚类结果: "+(i+1)+"   size: "+helpCenterList.get(i).size()+" :");
            Map <String ,Integer> mapName=new HashMap<String, Integer>();
            for(int j=0;j<helpCenterList.get(i).size();j++)
            {
                if(mapName.get(helpCenterList.get(i).get(j).getDataPointName())==null)
                    mapName.put(helpCenterList.get(i).get(j).getDataPointName(),1);
                else mapName.put(helpCenterList.get(i).get(j).getDataPointName(),(Integer) mapName.get(helpCenterList.get(i).get(j).getDataPointName()) +1);
            }
            for(String key:mapName.keySet()){
                System.out.println(key+":\t"+mapName.get(key));
            }
            mapName.clear();
        }
        System.out.println("所用的时间为："+(System.currentTimeMillis()-startTime)+"毫秒");
    }


}